import java.util.Arrays;

public class TextHeap {
    public int[] elem;
    public int usedSized;

    public TextHeap() {
        this.elem = new int[10];
    }
    
    public void initElem(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            elem[i] = arr[i];
            usedSized++;
        }
    }

    /*
    //创建大根堆
     */
    public void createHeap(){
        //找到这个完全二叉树中，最后一个父亲节点的下标：
        //最后一个节点的父亲节点，也是该二叉树的最后一个父亲节点
        //根据父亲节点个数，从后往前调整，可能之前调整过的，还会被调整
        for (int parent = (usedSized - 1 - 1 )/ 2;  parent >= 0 ; parent--) {
            //使用 usedSize 作为向下调整的最大边界
            shiftDown(parent,usedSized);
        }
    }

    private void shiftDown(int parent,int len){
        //最起码有左孩子
        int child = 2 * parent + 1;

        // 沿着树的高度去做调整
        while(child < len){
            //如果有右孩子时，得让 child 这个下标对应左右孩子最大值的下标
            if(child + 1 < len && elem[child] < elem[child + 1]){
                child++;
            }

            if(elem[child] > elem[parent]){
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
                parent = child;
                child = 2 * parent + 1;
            }else{
                break;
            }
        }
    }

    private void shiftUp(int child){
        int parent = (child - 1)/2;
        while(child > 0){
            if(elem[child] > elem[parent]){
                int temp = elem[child];
                elem[child] = elem[parent];
                elem[parent] = temp;
                child = parent;
                parent = (child - 1)/2;
            }else{
                break;
            }
        }
    }

    //堆的插入
    public void offer(int val){
        if(isFull()){
            //满了就扩容
            elem = Arrays.copyOf(elem,elem.length+5);
        }
        elem[usedSized++] = val;
        shiftUp(usedSized - 1);

    }
    private boolean isFull(){
        return usedSized == elem.length;
    }

    //堆的删除
    public void pop(){
        if(isEmpty()){
            return;
        }
        elem[0] = elem[usedSized - 1];
        usedSized--;
        //只需从0下标的这个父亲节点去向下调整就可以了
        shiftDown(0,usedSized);


    }
    private boolean isEmpty(){
        return usedSized == 0;
    }


}
